package me.mingshan.leetcode;

import java.util.*;

/**
 * https://leetcode.cn/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/description/
 * <p>
 * 2058. 找出临界点之间的最小和最大节点数
 * <p>
 * 链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。
 * <p>
 * 如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个  局部极大值点 。
 * <p>
 * 如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个  局部极小值点 。
 * <p>
 * 注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。
 * <p>
 * 给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance
 * 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1] 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：head = [3,1]
 * 输出：[-1,-1]
 * 解释：链表 [3,1] 中不存在临界点。
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入：head = [5,3,1,2,5,1,2]
 * 输出：[1,3]
 * 解释：存在三个临界点：
 * - [5,3,1,2,5,1,2]：第三个节点是一个局部极小值点，因为 1 比 3 和 2 小。
 * - [5,3,1,2,5,1,2]：第五个节点是一个局部极大值点，因为 5 比 2 和 1 大。
 * - [5,3,1,2,5,1,2]：第六个节点是一个局部极小值点，因为 1 比 5 和 2 小。
 * 第五个节点和第六个节点之间距离最小。minDistance = 6 - 5 = 1 。
 * 第三个节点和第六个节点之间距离最大。maxDistance = 6 - 3 = 3 。
 * 示例 3：
 * <p>
 * <p>
 * <p>
 * 输入：head = [1,3,2,2,3,2,2,2,7]
 * 输出：[3,3]
 * 解释：存在两个临界点：
 * - [1,3,2,2,3,2,2,2,7]：第二个节点是一个局部极大值点，因为 3 比 1 和 2 大。
 * - [1,3,2,2,3,2,2,2,7]：第五个节点是一个局部极大值点，因为 3 比 2 和 2 大。
 * 最小和最大距离都存在于第二个节点和第五个节点之间。
 * 因此，minDistance 和 maxDistance 是 5 - 2 = 3 。
 * 注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。
 * 示例 4：
 * <p>
 * <p>
 * <p>
 * 输入：head = [2,3,3,2]
 * 输出：[-1,-1]
 * 解释：链表 [2,3,3,2] 中不存在临界点。
 *
 * @author hanjuntao
 * @date 2025/7/29 0029
 */
public class L_2058_find_the_minimum_and_maximum_number_of_nodes_between_critical_points {
    public static void main(String[] args) {
        // 5,3,1,2,5,1,2
        ListNode head = new ListNode(5);
        head.next = new ListNode(3);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(1);
        head.next.next.next.next.next.next = new ListNode(2);

      //  System.out.println(Arrays.toString(nodesBetweenCriticalPoints(head))); // [1, 3]


        // 3,1
        head = new ListNode(3);
        head.next = new ListNode(1);

     //   System.out.println(Arrays.toString(nodesBetweenCriticalPoints(head))); // [-1, -1]

        // 2,2,1,3
        head = new ListNode(2);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        System.out.println(Arrays.toString(nodesBetweenCriticalPoints(head)));
    }

    /**
     * 思路：
     * <p>
     * 1. 本题需要找到所有的山峰&山底，并且统计其位置
     * 2. 然后根据其位置，找到最小和最大距离
     *
     * @param head
     * @return
     */
    public static int[] nodesBetweenCriticalPoints(ListNode head) {
        List<Integer> criticalPoints = new ArrayList<>();

        // 前一个
        ListNode pre = null;
        // 前前 一个
        ListNode prePre = null;
        ListNode cur = head;

        int i = 0;
        while (cur != null) {
            if (pre != null && prePre != null) {
                // 判断山峰与山底
                if (pre.val > cur.val && pre.val > prePre.val) {
                    criticalPoints.add(i - 1);
                } else if (pre.val < cur.val && pre.val < prePre.val) {
                    criticalPoints.add(i - 1);
                }
            }

            prePre = pre;
            pre = cur;

            cur = cur.next;
            i++;
        }

        if (criticalPoints.isEmpty() || criticalPoints.size() == 1) {
            return new int[] {-1, -1};
        }

        criticalPoints.sort(Comparator.comparingInt(o -> o));

        int maxD = criticalPoints.get(criticalPoints.size() - 1) - criticalPoints.get(0);
        int minD = Integer.MAX_VALUE;
        for (int j = 1; j < criticalPoints.size(); j++) {
            minD = Math.min(minD, criticalPoints.get(j) - criticalPoints.get(j - 1));
        }
        return new int[]{minD, maxD};
    }

}
